这道题是一道典型的搜索题，我们用表示蜗牛在这个点，走了步，当前的方向（起点的，特殊处理一下）。
当蜗牛确定一个方向后，我们就不断让它前进，同时记录它走过的格子，直到它遇到障碍，出界或者到达已走过的点停止。
如果蜗牛遇到障碍，我们就枚举每个方向，因为前方有障碍，后方已经走过，所以蜗牛只会向左或向右转，不需要特殊处理。
P2894 [USACO08FEB]酒店Hotel
这道题明显是线段树的板题，至于考试时因为懒标记的小问题只有20分，我也很无奈。
进入正题，既然要修改查询区间内连续的一段元素，似曾相识的感觉。
我们等价的把空房子看为1，住人的房子看为0。
P5427 [USACO19OPEN]Left Out
发布于
2020-10-14
|
4分钟
|
707字数
为了书写方便，我们将′L′表示为0，′R′表示为1。
现在题目转化为给你一个01矩阵，每次可将一行或一列的01反转，要求最后只有一个1或只有一个0，问能否办到。
现在，我们将第一行和第一列的元素全变为1（0也可以），这个很好办到，翻转第一行的元素就将该元素所在列翻转，列同理。
P3232 [HNOI2013]游走
这道题边的数量最高是10000多，而点只有500，这提醒我们，我们不能直接对边求期望，而是点。
设Expection[u]表示点u的期望走过次数，Degree[u]表示点u的度数。
那么，
CF559C Gerald and Giant Chess
如果没有不能走到的点，这道题就非常简单了。我们只需向下走h−1步，向右走w−1步，就可到达右下角。在这h+w−2步中，我们选h−1向下走，那么答案为Ch+w−2h−1。
但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案，即
CF167E Wizards and Bets
首先，我们将所有源点与汇点筛出来，然后从每一个源点dfs求出它到各汇点的路径数，题目中保证源点与汇点数量相同，我们记为cnt。
那么，我们可以得到一个cnt∗cnt的矩阵。
先考虑路径不相交的情况（似乎大家思路都是这样），题目求的是一个排列的逆序对数，记为τ(σ)。那么，题目等价于求：
0%